package com.example.myletcodelearing.one

import java.lang.StringBuilder
import java.util.*
import kotlin.collections.HashMap
import kotlin.math.abs


/**
 * @author tgw
 * @date 2022/11/7
 * https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/
 *
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
请你返回纸上能写出的字典序最小的字符串。

 

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

fun main(args: Array<String>) {
    var op = Solution18.Solution()
    var nums1 = "zzabc"
    var result = op.robotWithString(nums1)

    print("打印：$result")

}

private class Solution18 {
    internal class Solution {
        //求出栈序列的最小字典序
        //持续检查栈顶元素 c, 设还未入栈的字符中，字典序最小的字符是 m ,遍历处理
        //case1: c≤m：此时弹出 c 最优。
        //case2: c>m：此时不弹出 c，等待后续更小的字符入栈。
        fun robotWithString(s: String): String {
            val sb = StringBuilder()
            val st: Stack<Char> = Stack()
            val len = s.length
            val helper = IntArray(len + 1)
            helper[len] = ('z' - 'a' + 1)
            for (i in len - 1 downTo 0) {
                helper[i] = Math.min(helper[i + 1], s[i] - 'a')
            }
            for (i in 0 until len) {
                st.push(s[i])
                while (!st.isEmpty() && st.peek() - 'a' <= helper[i + 1]) {
                    sb.append(st.pop())
                }
            }
            return sb.toString()
        }
    }

}
